package com.hardy.leetcode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * User: Ruijie Date: 2016/9/1
 */
public class BSTTreeConvertLinkList {
    public static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val){
            this.val=val;
        }
    }

    //left指针指向前驱，right指针指向后继
    public static TreeNode _BSTTreeConvertLinkList(TreeNode root){
        if(root==null){
            return null;
        }
        TreeNode leftE=_BSTTreeConvertLinkList(root.left);
        TreeNode rightE=_BSTTreeConvertLinkList(root.right);
        TreeNode leftS=leftE!=null?leftE.right:null;
        TreeNode rightS=rightE!=null?rightE.right:null;
        if(leftE!=null&&rightE!=null){
            root.right=rightS;
            root.left=leftE;
            leftE.right=root;
            rightS.left=root;
            rightE.right=leftS;
            return rightE;
        }else if(leftE!=null){
            root.left=leftE;
            leftE.right=root;
            root.right=leftS;
            return root;
        }else if(rightE!=null){
            rightE.right=root;
            rightS.left=root;
            root.right=rightS;
           return rightE;
        }else{
            root.right=root;
            return root;
        }

    }
    public static TreeNode process(TreeNode head) {
        if (head == null) {
            return null;
        }
        TreeNode leftE = process(head.left); // left end
        TreeNode rightE = process(head.right); // right end
        TreeNode leftS = leftE != null ? leftE.right : null; // left start
        TreeNode rightS = rightE != null ? rightE.right : null; // right start
        if (leftE != null && rightE != null) {
            leftE.right = head;
            head.left = leftE;
            head.right = rightS;
            rightS.left = head;
            rightE.right = leftS;
            return rightE;
        } else if (leftE != null) {
            leftE.right = head;
            head.left = leftE;
            head.right = leftS;
            return head;
        } else if (rightE != null) {
            head.right = rightS;
            rightS.left = head;
            rightE.right = head;
            return rightE;
        } else {
            head.right = head;
            return head;
        }
    }
    public static TreeNode convert2(TreeNode head) {
        if (head == null) {
            return null;
        }
        TreeNode last = process(head);
        head = last.right;
        last.right = null;
        return head;
    }
    public static TreeNode convert1(TreeNode root){
        if(root==null){
            return null;
        }
        Queue<TreeNode> q=new LinkedList<TreeNode>();
        inOrderTree(root,q);
        TreeNode head=q.poll();
        TreeNode pre=head;
        while(!q.isEmpty()){
            TreeNode cur=q.poll();
            cur.left=pre;
            pre.right=cur;
            pre=cur;
        }
        pre.right=null;
        return head;
    }

    private static void inOrderTree(TreeNode root, Queue<TreeNode> q) {
        if(root!=null){
            inOrderTree(root.left,q);
            q.offer(root);
            inOrderTree(root.right,q);
        }
    }

    public static void printDoubleLinkedList(TreeNode head) {
        System.out.print("Double Linked List: ");
        TreeNode end = null;
        while (head != null) {
            System.out.print(head.val + " ");
            end = head;
            head = head.right;
        }
        System.out.print("| ");
        while (end != null) {
            System.out.print(end.val + " ");
            end = end.left;
        }
        System.out.println();
    }
    public static void main(String[] args) {
        TreeNode root=new TreeNode(1);
        root.left=new TreeNode(2);
        root.right=new TreeNode(5);
        root.left.left=new TreeNode(3);
        root.left.right=new TreeNode(4);
        root.right.left=new TreeNode(6);
        root.right.right=new TreeNode(7);


        TreeNode head = new TreeNode(5);
        head.left = new TreeNode(2);
        head.right = new TreeNode(9);
        head.left.left = new TreeNode(1);
        head.left.right = new TreeNode(3);
        head.left.right.right = new TreeNode(4);
        head.right.left = new TreeNode(7);
        head.right.right = new TreeNode(10);
        head.left.left = new TreeNode(1);
        head.right.left.left = new TreeNode(6);
        head.right.left.right = new TreeNode(8);
        TreeNode head1=convert1(head);
       printDoubleLinkedList(head1);
    }
}
